package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
https://leetcode.cn/problems/validate-binary-search-tree/description/

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]
输出：true

示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
 */
class leetcode_98 {
    @Test
    fun test_1() {
        val root = TreeNode(2)
        root.left = TreeNode(1)
        root.right = TreeNode(3)

        val actual = isValidBST(root)
        val expect = true
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(5)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n6 = TreeNode(6)
        root.left = n1
        root.right = n4
        n4.left = n3
        n4.right = n6

        val actual = isValidBST(root)
        val expect = false
        Assert.assertEquals(expect, actual)
    }

    fun isValidBST(root: TreeNode?): Boolean {
        // 左树的所有节点 < 当前节点 < 右树的所有节点
        // return isValidBST1(root)
        return isValidBST2(root)
    }

    var prev: TreeNode? = null
    fun isValidBST1(root: TreeNode?): Boolean {
        // 中序遍历 - 递归 + 双指针法（当前节点，前一个节点）
        // T - N
        // S - 1

        // 结束条件
        if (null == root) {
            // 二叉搜索树也可以为null
            return true
        }

        // 左
        val isLeftValid = isValidBST1(root.left)
        if (!isLeftValid) {
            return false
        }

        // 中
        prev?.let{
            if(root.`val` <= it.`val`){
                return false
            }
        }
        prev = root

        // 右
        val isRightValid = isValidBST1(root.right)
        return isRightValid
    }

    fun isValidBST2(root: TreeNode?): Boolean {
        // 中序遍历（左 中 右） - 统一迭代法 + 双指针法（当前节点，前一个节点）
        // 栈（右中左）
        // T - N
        // S - N
        if (null == root) {
            return false
        }

        var pre: TreeNode? = null
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>() // 存放前面的节点
        stack.push(Pair<TreeNode, Boolean>(root, false))

        while (!stack.isEmpty()) {
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node = pair.first
            val visited = pair.second

            if (visited) {
                // when pre = 1, node = 2
                if (null != pre) {
                    if (pre.`val` >= node.`val`) {
                        return false
                    }
                }
                pre = node
                continue
            }

            // 右

            node.right?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }
            // 中
            stack.push(Pair<TreeNode, Boolean>(node, true))

            // 左
            node.left?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }
        }
        return true
    }
}